package main

func partition(s string) [][]string {
	result := make([][]string, 0)
	dp := make([][]bool, len(s))

	for i := 0; i < len(s); i++ {
		dp[i] = make([]bool, len(s))
	}

	getRepeatStr := func() {
		for i := 0; i < len(s); i++ {
			for j := 0; j <= i; j++ {
				if i-j < 2 {
					if s[i] == s[j] {
						dp[j][i] = true
					}
					continue
				}

				if s[i] == s[j] && dp[j+1][i-1] {
					dp[j][i] = true
				}

			}

		}
	}

	getRepeatStr()

	var dfs func(str string, idX int, ret []string)

	dfs = func(str string, idX int, ret []string) {
		if idX >= len(str) {
			temp := make([]string, 0)
			for i := 0; i < len(ret); i++ {
				temp = append(temp, (ret)[i])
			}

			result = append(result, temp)
		}

		for j := idX; j < len(str); j++ {
			if dp[idX][j] {
				ret = append(ret, str[idX:j+1])
				dfs(str, j+1, ret)
				ret = (ret)[:len(ret)-1]
			}
		}

	}

	dfs(s, 0, []string{})

	return result
}

func main() {
	partition("abbab")
}
